package com.leetcode.图.图的同构;

import java.util.Arrays;

public class GraphUtils {

	/**
	 * 判断两个图是否同构
	 * 
	 * @param g1
	 * @param g2
	 * @return false：不同构；true：同构
	 */
	public static boolean isIsomorphic(Graph g1, Graph g2) {
		// 节点数不相等，肯定不同构
		if (g1.getNodesSize() != g2.getNodesSize())
			return false;
		// 如果两个图的统计度数表不一样，则肯定不同构
		if (!compareTotalDegrees(g1, g2))
			return false;
		int size = g1.getNodesSize();
		int[] nodeList = new int[size];
		boolean[] visit = new boolean[size];
		for (int i = 0; i < size; i++) {
			nodeList[0] = i;// 第一个节点的序号
			visit[i] = true;// 序号为i+1的节点已经访问过了
			if (dfs(g1, g2, size, 1, nodeList, visit))
				return true;
			visit[i] = false;// 上面的if条件不成立，要更改第一个节点的序号，需要将访问过的节点设置为false
		}
		return false;
	}

	/**
	 * 比较两个图的统计度数表，两个图的统计度数表一样，有可能同构，不一样，肯定不同构
	 * @param g1
	 * @param g2
	 * @return false:肯定不同构；true：有可能同构
	 */
	public static boolean compareTotalDegrees(Graph g1, Graph g2) {
		if (g1.getNodesSize() != g1.getNodesSize())
			return false;
		int[] g1Degrees = g1.getTotalDegrees();
		int[] g2Degrees = g2.getTotalDegrees();
		int size = g1.getNodesSize();
		for (int i = 0; i < size; i++) {
			if (g1Degrees[i] != g2Degrees[i])
				return false;
		}
		return true;
	}

	/**
	 * 深搜遍历，改变图g1的节点排序，将最终的邻接矩阵与图g2的邻接矩阵判断是否一样，一样则是同构，不一样则不同构
	 * 
	 * @param g1
	 * @param g2
	 * @param size     总的节点数
	 * @param cur      已经访问了cur个节点了，如果cur==size表示，所有节点都已经访问过了
	 * @param nodeList 一次结果的节点序列
	 * @param visit    判断一个节点是否被访问过
	 * @return 最外层的dfs：返回true，两个图同构；返回false，两个图不同构。
	 *         其他层的dfs：返回true，两个图同构；返回false，不足以证明两个图不同构，继续深搜
	 */
	private static boolean dfs(Graph g1, Graph g2, int size, int cur, int[] nodeList, boolean[] visit) {
		if (cur == size) {
			return compare(g1, nodeList, g2);
		}
		int[] degree1 = g1.getNodeOfDegree();
		int[] degree2 = g2.getNodeOfDegree();
		for (int i = 0; i < size; i++) {
			if (visit[i])
				continue;// 找出没有被访问过的节点序号，作为当前节点的序号
			// 判断当前的节点的度数，更换为序号i+1时，与g2对应的i+1序号的度数相不相等，相等，则可以往下dfs，不等，说明i是不符合的
			if (degree1[cur] == degree2[i]) {
				nodeList[cur] = i;
				visit[i] = true;
				if (dfs(g1, g2, size, cur + 1, nodeList, visit))
					return true;// 如果为true，则直接返回结果
				visit[i] = false;// 回溯的时候，需要把访问过的节点，设置为false
			}
		}
		return false;
	}

	/**
	 * 将图一的节点序列换成nodeList，比较与图二的邻接矩阵是否一致
	 * @param g1
	 * @param nodeList
	 * @param g2
	 * @return
	 */
	public static boolean compare(Graph g1, int[] nodeList, Graph g2) {
		if (g1.getNodesSize() != g2.getNodesSize())
			return false;
		int[][] matrix1 = g1.getMatrix();
		int[][] matrix2 = g2.getMatrix();
		int size = g1.getNodesSize();
		int[][] newMatrix = new int[size][size];
		for (int i = 0; i < size; i++) {
			for (int j = i + 1; j < size; j++) {
				if (matrix1[i][j] == 1) {
					newMatrix[nodeList[i]][nodeList[j]] = 1;
					newMatrix[nodeList[j]][nodeList[i]] = 1;
				}
			}
		}
		for(int i = 0;i < size;i++) {
			for(int j = i + 1;j < size;j++) {
				if(newMatrix[i][j] != matrix2[i][j]) return false;
			}
		}
		return true;
	}

	// 打印邻接矩阵
	public static void printMatrix(int[][] matrix) {
		int size = matrix.length;
		if (size == 0)
			System.out.println("矩阵为空");
		for (int[] arr : matrix) {
			System.out.println(arrToString(arr));
		}
	}

	private static String arrToString(int[] a) {
		if (a == null)
			return "null";
		int iMax = a.length - 1;
		if (iMax == -1)
			return "数组为空";

		StringBuilder b = new StringBuilder();
//		b.append("{");
		for (int i = 0;; i++) {
			b.append(a[i]);
			if (i == iMax) {
//				b.append("}");
				return b.toString();
			}
			b.append(" ");
		}
	}
}
